Năm 1995, giải lần đầu tiên được tổ chức với tên gọi Giải Mai vàng. Giải vẫn giữ thể lệ là do bạn đọc báo Người lao động bình chọn giống như giải thưởng Bình chọn Văn nghệ sĩ được yêu thích nhất trong năm trước đó, nhưng có điểm khác là kết quả bình chọn này sẽ được thẩm định lại bởi Hội đồng Nghệ thuật gồm các nghệ sĩ đứng đầu các hội nghệ thuật chuyên ngành, các nghệ sĩ có tên tuổi, uy tín.

Giải Mai vàng đã được cải tiến chuyên nghiệp hơn ở lần thứ 9 giải được tổ chức vào năm 2003, hình thức bình chọn tiện lợi hơn, đã có phần mềm riêng biệt dùng cho việc kiểm phiếu. Số lượng độc giả tham gia bình chọn lên đến trên 50.000 người. Lễ trao giải cũng đã được dàn dựng chuyên nghiệp hơn. Trung tâm Ca nhạc Lan Anh đã tài trợ khoản sân khấu, âm thanh, ánh sáng cho buổi lễ trao giải thay vì tổ chức phát giải ở sân khấu ngoài trời vào ban ngày như các lần trước đó ở Khu Du lịch Văn hóa Suối Tiên hay Công viên Văn hóa Đầm Sen. Trung tâm Băng nhạc Rạng Đông cũng giúp dàn dựng chương trình hoàn toàn miễn phí. Cùng với đó, ê kíp thực hiện gồm đạo diễn Huỳnh Phúc Điền, nhạc sĩ Lê Quang và họa sĩ Lê Trường Tiếu cũng như các ca sĩ khách mời đều gần như không nhận thù lao.[2] Đây là lần đầu tiên lễ trao giải của Giải Mai vàng có tổ chức bán vé với hơn 3 ngàn khán giả, các vị khách mời cùng với gần 100 văn nghệ sĩ đã đến tham dự và cũng là lần đầu tiên được Đài Truyền hình Thành phố Hồ Chí Minh truyền hình trực tiếp phục vụ khán giả xem đài.

Trong dịp kỷ niệm 10 năm Giải Mai vàng, ở Giải Mai vàng lần thứ 10 - 2004, Ban Tổ chức đã quyết định đổi mới trong khâu bình chọn, lần đầu tiên bạn đọc có thể tham gia bình chọn trên báo Người lao động điện tử bên cạnh hình thức bình chọn thông qua ấn bản báo in phát hành hàng ngày. Bên cạnh đó, Giải Mai vàng từ lần tổ chức này đã có được logo chính thức. Buổi lễ trao giải có sự hiện diện của hơn 4 ngàn khán giả và hơn 100 nghệ sĩ trong cả nước.

Giải Mai vàng đã được cải tiến qua từng năm theo hướng chuyên nghiệp hơn trong khâu tổ chức. Tuy nhiên, kết quả bình chọn trong những năm gần đây đã vấp phải không ít những ý kiến không đồng tình từ dư luận với những cá nhân, tác phẩm chưa thật sự nổi bật nhưng vẫn đạt giải.[3][4]